package interview.questions.二维数组中的查找;

/**
 * 问题：
 * <p>
 * 在一个二维数组中（每个一维数组的长度相同），
 * 每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。
 * <p>
 * 要求：
 * <p>
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 */
public class Solution {
    /**
     * 解决方案：
     * <p>
     * 首先选取数组中右上角的数字。
     * 如果该数字等于要查找的数字，查找过程结束；
     * 如果该数字大于要查找的数字，剔除这个数字所在的列；
     * 如果该数字小于要查找的数字，剔除这个数字所在的行。
     * <p>
     * 也就是说如果要查找的数字不在数组的右上角，
     * 则每一次都在数组的查找范围中剔除一行或者一列，
     * 这样每一步都可以缩小查找的范围，直到找到要查找的数字，
     * 或者查找范围为空。
     *
     * @param target 基准数
     * @param array  需排序的二维数组
     * @return
     */
    public static boolean Find(int target, int[][] array) {
        int row = 0;
        int col = array[0].length - 1;
        boolean flag = false;
        while (row < array.length && col >= 0) {
            if (array[row][col] == target) {
                flag = true;
                break;
            } else if (array[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return flag;
    }
}
